package xyz.scootaloo.oj.leetcode;

import xyz.scootaloo.console.app.support.Tester;

import java.util.*;
import java.util.stream.Collectors;

/**
 * 动态规划
 *
 * @author flutterdash@qq.com
 * @since 2021/3/26 20:59
 */
public class P139 {

    public boolean wordBreak(String s, List<String> wordDict) {
        // 收集数据
        int len = s.length();
        // key:能以此下标结束的单词  value:这些单词的开始位置
        Map<Integer, List<Integer>> cache = new HashMap<>();
        for (int i = 0; i<len; i++) {
            for (String word : wordDict) {
                int endIdx = getWordEndIdx(s, word, i);
                if (endIdx == -1)
                    continue;
                List<Integer> startPoints = cache.get(endIdx);
                if (startPoints == null) {
                    startPoints = new ArrayList<>();
                    startPoints.add(i);
                    cache.put(endIdx, startPoints);
                } else {
                    startPoints.add(i);
                }
            }
        }

        boolean[] dp = new boolean[len];
        for (int i = 0; i<len; i++) {
            List<Integer> startPoints = cache.get(i);
            if (startPoints != null) {
                for (Integer point : startPoints) {
                    if (point == 0 || dp[point - 1]) {
                        dp[i] = true;
                        break;
                    }
                }
            }
        }

        return dp[len - 1];
    }

    private int getWordEndIdx(String source, String word, int offset) {
        int end = word.length();
        if ((source.length() - offset) < end)
            return -1;
        end += offset;
        for (int wordIdx = 0; offset<end; offset++, wordIdx++) {
            if (source.charAt(offset) != word.charAt(wordIdx))
                return -1;
        }
        return (end - 1);
    }

    public static void main(String[] args) {
        String[] dict_input_1 = {"leet", "code"};
        String source_input_1 = "leetcode";

        String[] dict_input_2 = {"apple", "pen"};
        String source_input_2 = "applepenapple";

        String[] dict_input_3 = {"cats", "sand", "dog"};
        String source_input_3 = "catsandog";

        String[] dict_input_4 = {"car", "ca", "rs"};
        String source_input_4 = "cars";

        Tester.createTest(Input::testFun)
                .addCase(new Input(source_input_1, dict_input_1), true)
                .addCase(new Input(source_input_2, dict_input_2), true)
                .addCase(new Input(source_input_3, dict_input_3), false)
                .addCase(new Input(source_input_4, dict_input_4), true)
                .test();
    }

    private static class Input {
        private static final P139 INSTANCE = new P139();
        private static boolean testFun(Input input) {
            return INSTANCE.wordBreak(input.source, input.wordDict);
        }

        private final String source;
        private final List<String> wordDict;
        private Input(String source, String[] wordDict) {
            this.source = source;
            this.wordDict = Arrays.stream(wordDict).collect(Collectors.toList());
        }

        @Override
        public String toString() {
            return "Input{" +
                    "source='" + source + '\'' +
                    ", wordDict=" + wordDict +
                    '}';
        }
    }

}
